package com.lihepeng.leecode.frequency.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 重新构建二叉树
 * 2022年5月10日
 *描述
 * 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
 * 关联leetcode
 * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 *
 */
public class Solution40 {
    Map<Integer,Integer> indexMap = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        for (int i=0;i<vin.length;i++) {
            indexMap.put(vin[i],i);
        }
        return myBuildMap(pre,vin,0,n-1,0,n-1);
    }

    private TreeNode myBuildMap(int[] pre, int[] vin, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft>preRight) {
            return null;
        }
        // 前序 遍历的第一个节点就是根节点
        int pRootNode = preLeft;
        // 定位在中序遍历的位置
        Integer inOrderRoot = indexMap.get(pre[pRootNode]);
        TreeNode root = new TreeNode(pre[pRootNode]);
        // 计算左子树的节点数量
        int leftTreeCount = inOrderRoot-inLeft;
        // 递归的构建左子树，并且链接到根节点上来
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildMap(pre, vin, preLeft + 1, preLeft + leftTreeCount, inLeft, inRight - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildMap(pre, vin, preLeft + leftTreeCount + 1, preRight, inLeft + 1, inRight);
        return root;

    }
}
